# 考点：背包问题
"""
题目描述
小明每周上班都会拿到自己的工作清单，工作清单内包含 n 项工作，每项工作都有对应的耗时时间（单位 h）和报酬，工作的总报酬为所有已完成工作的报酬之和，那么请你帮小明安排一下工作，保证小明在指定的工作时间内工作收入最大化。

输入描述
T 代表工作时长（单位 h， 0 < T < 1000000），
n 代表工作数量（ 1 < n ≤ 3000）。
接下来是 n 行，每行包含两个整数 t，w。
t 代表该工作消耗的时长（单位 h， t > 0），w 代表该项工作的报酬。

输出描述
输出小明指定工作时长内工作可获得的最大报酬。

示例1
输入
40 3
20 10
20 20
20 5

输出
30

解题思路
本题是典型的01背包问题，其中：

工作时长 ( T ) 相当于背包的承重。
每一项工作相当于每件物品。
工作消耗的时长相当于物品的重量。
工作的报酬相当于物品的价值。
思路
初始化与输入：

首先读入工作时间 ( T ) 和工作数量。
读入每项工作的耗时和报酬，存储在二维数组中。
动态规划：

确定所有工作中耗时最短的那个 ( \text{min_time} )，以便从该时间开始计算dp数组。
初始化一个二维dp数组 ( \text{dp}[i][j] )，其中 ( \text{dp}[i][j] ) 表示前 ( i ) 项工作在 ( j ) 时间内能获得的最大报酬。
动态规划执行：

使用两个嵌套的for循环遍历工作项 ( i ) 和时间 ( j )。
对于第 ( i ) 项工作：
如果耗时 ( \text{tasks}[i-1][0] ) 大于 ( j )，则无法完成该项工作，此时最大报酬为 0。
否则，能完成该项工作，最大报酬为 ( \text{tasks}[i-1][1] ) 加上前 ( i-1 ) 项工作在 ( j-\text{tasks}[i-1][0] ) 时间内能获得的最大报酬。
更新dp数组，( \text{dp}[i][j] = \max(\text{dp}[i-1][j], \text{current}) )，其中 (\text{current}) 是如果包含当前工作所得到的报酬。
输出结果：

输出 ( \text{dp}[n][T] )，表示前 ( n ) 项工作在 ( T ) 时间内能获得的最大报酬。

作者：左雀斑
链接：https://www.nowcoder.com/discuss/687577854518853632
来源：牛客网
"""


"""
0-1 背包问题（最经典）
🔸 问题描述
有 n 个物品，第 i 个物品重量为 w[i]，价值为 v[i]
背包最大承重为 W
每个物品最多选一次
求：不超过重量 W 的前提下，能获得的 最大总价值
🔸 动态规划思路
状态定义（二维）：
dp[i][j] = 考虑前 i 个物品，背包容量为 j 时的最大价值

if j >= w[i-1]:
    dp[i][j] = max( dp[i-1][j], dp[i-1][j - w[i-1]] + v[i-1] )
else:
    dp[i][j] = dp[i-1][j]
    
初始化：
dp[0][j] = 0（没有物品，价值为 0）
答案：
dp[n][W]

✅ Python 实现（空间优化版 → 一维数组）
def knapsack_01(weights, values, W):
    dp = [0] * (W + 1)  # dp[w] 表示容量为 w 时的最大价值
    
    for i in range(len(weights)):
        # 逆序遍历！防止重复使用同一物品
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[W]

# 测试
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
W = 8
print(knapsack_01(weights, values, W))  # 输出: 10
✅ 关键：内层循环必须逆序！ 
"""
T,n = map(int,input().split())  # 输入最大工作时长T，和工作数目n

dp = [0] * (T + 1) # 初始化数组，创建长度为 T+1 的一维数组，初始全 0

for _ in range(n):
    t,w = map(int,input().split())  # 输入每项工作的时间、报酬

    for tt in range(T, t-1, -1):  # 动态规划，从后往前遍历以避免重复使用
        dp[tt] = max(dp[tt], dp[tt - t] + w)
        # tt - t 必须 ≥ 0 且 ≤ T
        # 换句话说：DP 状态 dp[tt] 本身就代表“总时间 ≤ tt”的最优解，天然不会超限。

print(dp[T])


# # 牛客网
# import sys
# input = sys.stdin.readline
#
# work_time, n = map(int, input().split()) # 工作时间和工作数量
# tasks = [] # 存储每项工作的耗时时间和报酬
# for i in range(n):
#     tasks.append(list(map(int, input().split())))
#
# min_time = float('inf') # 找到所有工作中耗时最短的那个min_time
# for task in tasks:
#     min_time = min(min_time, task[0])
#
# dp = [[0] * (work_time + 1) for _ in range(n + 1)] # 初始化dp数组
# for i in range(1, n + 1):
#     for j in range(min_time, work_time + 1):
#         last = dp[i - 1][j] # 上一项工作在j时间内能获得的最大报酬
#         current = 0 if tasks[i - 1][0] > j else tasks[i - 1][1] + dp[i - 1][j - tasks[i - 1][0]] # 当前工作在j时间内能获得的最大报酬
#         dp[i][j] = max(last, current) # 取上一项工作和当前工作在j时间内能获得的最大报酬的最大值
#
# print(dp[n][work_time]) # 输出前n项工作在T时间内能获得的最大报酬
#
# 123456789101112131415161718192021
#
#
# # ----------------------------------------------------------------------------------------------------------------------------
# # T 工作时长,  n 工作数量
# T, n = map(int, input().split())
#
# # 初始化dp数组
# dp = [0] * (T + 1)
#
# # 循环读取工作消耗的时长t和工作的报酬
# for _ in range(n):
#     t, w = map(int, input().split())
#
#     # 动态规划，从后往前遍历以避免重复使用
#     for cap in range(T, t - 1, -1):
#         dp[cap] = max(dp[cap], dp[cap - t] + w)
#
# # 输出结果
# print(max(dp))

